package xyz.scootaloo.oj.leetcode;

import xyz.scootaloo.console.app.support.Tester;

/**
 * 动态规划
 * 硬币找零
 * @author flutterdash@qq.com
 * @since 2021/3/24 20:29
 */
public class P279 {

    /**
     * squares  1, 4, 9
     *
     * numbers  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
     *
     * dp       1, 2, 3, 1, 2, 2, 4, 2, 3, 4,  5 , 3
     *
     * @param n number
     * @return int
     */
    public int numSquares(int n) {
        if (n < 4)
            return n;
        int limit = 100;
        int[] squares = squares(limit);
        int[] dp = new int[n + 1];
        dp[0] = Integer.MAX_VALUE;
        dp[1] = 1;
        for (int i = 2; i<=n; i++) {
            int bound = n;
            if (i < squares.length / 2) {
                for (int j = 0; j<=limit; j++) {
                    if (squares[j] > i) {
                        bound = --j;
                        break;
                    }
                }
            } else {
                for (int j = limit; j>=0; j--) {
                    if (squares[j] <= i) {
                        bound = j;
                        break;
                    }
                }
            }
            dp[i] = getFitNumber(dp, squares, i, bound);
        }
        return dp[n];
    }

    private int getFitNumber(int[] dp, int[] squares, int n, int bound) {
        if (squares[bound] == n)
            return 1;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i<=bound; i++) {
            int current = dp[n - squares[i]];
            if (current < min)
                min = current;
        }
        return min + 1;
    }

    private int[] squares(int limit) {
        int[] squares = new int[limit + 1];
        for (int i = 0; i<=limit; i++)
            squares[i] = i * i;
        return squares;
    }

    public static void main(String[] args) {
        int input_1 = 101;
        Tester.createTest(new P279()::numSquares)
                .addCase(input_1, 3)
                .test();
    }

}
